package org.shopen.ai.puremvc.model.algo.bfs
{
	import mx.collections.ArrayCollection;
	
	import org.shopen.ai.puremvc.model.algo.FailureResult;
	import org.shopen.ai.puremvc.model.algo.ISearchAlgo;
	import org.shopen.ai.puremvc.model.algo.ISearchNode;
	import org.shopen.ai.puremvc.model.algo.ISearchProblem;
	import org.shopen.ai.puremvc.model.algo.ISearchResult;
	import org.shopen.ai.puremvc.model.algo.containers.FIFOQueue;
	import org.shopen.ai.puremvc.model.algo.containers.HashTable;
	import org.shopen.ai.puremvc.model.algo.containers.IHashTable;
	import org.shopen.ai.puremvc.model.algo.containers.IQueue;

	public class BreadthFirstSearchAlgo implements ISearchAlgo
	{
		protected var explored : IHashTable = new HashTable(100);
		protected var frontier : IQueue = new FIFOQueue();
		
		[Bindable]
		private var _title : String = "Breadth First Search";
		[Bindable]
		public function get title() : String
		{
			return this._title;
		}
		public function set title(value : String) : void
		{
			this._title = value;
		}
		
		
		public function BreadthFirstSearchAlgo()
		{
		}
		
		protected function clear() : void
		{
			explored.clear();
			frontier = new FIFOQueue();
		}

		public function toString():String
		{
			return "Breadth First Search";
		}
		
		public function search(problem:ISearchProblem):ISearchResult
		{
			clear();
			
			frontier.push(problem.intialNode);
			var currNode : ISearchNode = frontier.pop();
			while (currNode != null)
			{
				explored.add(currNode);
				if (problem.isGoal(currNode))
				{
					return currNode;
				}
				else
				{
					var expandList : ArrayCollection = problem.expand(currNode);
					for each (var expNode : ISearchNode in expandList)
					{
						if (!explored.contains(expNode))
						{
							frontier.push(expNode);
						}
					}
				}
				currNode = frontier.pop();
			}
			return new FailureResult("Not found after whole tree explored");
		}
		
	}
}